package com.dylon.sort;

import java.util.Arrays;

/**
 * 堆排序
 */
public class HeapSort {

    public static void main(String[] args) {
        int[] a = new int[]{2,5,3,1,4,13,11,26,24};
        heapSort(a);
    }

    private static void heapSort(int[] arr) {
        System.out.println("原始数组为     ："+Arrays.toString(arr));
        int[] val = new int[arr.length]; // 临时储存结果
        //step1建堆
        creatHeap(arr);
        System.out.println("建堆后的序列为 ："+Arrays.toString(arr));
        // step2 进行n次取值建堆，每次取堆顶元素放到val数组中，最终结果即为一个递增排序的序列
        for (int i=0; i<arr.length; i++) {
            val[i]=arr[0];//将堆顶放入结果中
            arr[0]=arr[arr.length-1-i];//删除堆顶元素，将末尾元素放到堆顶
            shiftDown(arr, 0, arr.length-i);//将这个堆调整为合法的小根堆，注意(逻辑上的)长度有变化
        }
        //数值克隆复制
        for (int i=0; i<arr.length; i++) {
            arr[i]=val[i];
        }
        System.out.println("堆排序后的序列为："+Arrays.toString(arr));
    }

    //将数组创建成堆
    private static void creatHeap(int[] arr) {
        for (int i=arr.length/2; i>=0; i--) {
            shiftDown(arr, i,arr.length);
        }
    }

    //下移交换 把当前节点有效变换成一个堆(小根)
    private static void shiftDown(int[] arr,int index,int len) { //0 号位置不用
        int leftchild = index*2+1;//左孩子
        int rightchild = index*2+2;//右孩子
        if (leftchild>=len) {
            return;
        } else if (rightchild<len && arr[rightchild]<arr[index] && arr[rightchild]<arr[leftchild]) { // 右孩子在范围内并且应该交换
            swap(arr, index, rightchild); // 交换节点值
            shiftDown(arr, rightchild, len); // 可能会对孩子节点的堆有影响，向下重构
        } else if (arr[leftchild]<arr[index]) { // 交换左孩子
            swap(arr, index, leftchild);
            shiftDown(arr, leftchild, len);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /*
    堆是一棵完全二叉树
        大根堆和小根堆：完全二叉树中所有节点均大于(或小于)它的孩子节点
            如果所有节点「大于」孩子节点值，那么这个堆叫做「大根堆」，堆的最大值在根节点
            如果所有节点「小于」孩子节点值，那么这个堆叫做「小根堆」，堆的最小值在根节点
              2                                  10
         3          4                      9            8
      5     8    6     7               7       6     5      4

    堆排序首先就是「建堆」，然后再是调整。对于二叉树(数组表示)，我们从下往上进行调整，
    从「第一个非叶子节点」开始向前调整，对于调整的规则如下：
        建堆是一个O(n)的时间复杂度过程，建堆完成后就需要进行删除头排序。给定数组建堆(creatHeap)
        ①从第一个非叶子节点开始判断交换下移(shiftDown)，使得当前节点和子孩子能够保持堆的性质
        ②但是普通节点替换可能没问题，对如果交换打破子孩子堆结构性质，那么就要重新下移(shiftDown)被交换的节点一直到停止。
                16                              6                       6
            6       14                     16       14              9        14
        9       12                      9       12               16     12
            16和6交换                      交换之后影响子堆
                                            16继续和9交换

        堆构造完成，取第一个堆顶元素为最小(最大)，剩下左右孩子依然满足堆的性值，但是缺个堆顶元素，如果给孩子调上来，
            可能会调动太多并且可能破坏堆结构。
        ①所以索性把最后一个元素放到第一位。这样只需要判断交换下移(shiftDown）,不过需要注意此时整个堆的大小已经发生了变化，
            我们在逻辑上不会使用被抛弃的位置，所以在设计函数的时候需要附带一个堆大小的参数。
        ②重复以上操作，一直堆中所有元素都被取得停止。


        而堆算法复杂度的分析上，之前建堆时间复杂度是O(n)。而每次删除堆顶然后需要向下交换，每个个数最坏为logn个
        这样复杂度就为O(nlogn).总的时间复杂度为O(n)+O(nlogn)=O(nlogn)

     */

}
